package com.sakura.二分答案;

public class Code275_H指数II {


    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0;
        int right = n + 1;
        while (left + 1 < right) {
            // 只有mid篇论文被mid次引用
            int mid = left + (right - left) / 2;
            // 由于升序排序，citations[n - mid] 位置的引用次数大于等于mid，
            // 则说明 [n-mid, n-1] 范围内都是满足“mid篇论文被mid次引用”
            // 那么就移动left，继续二分
            if (citations[n - mid] >= mid) {
                left = mid;
            } else {
                right = mid; // (left, n-mid-1)
            }
        }
        return left;
    }


    // n log n
    public int hIndex_1(int[] citations) {
        int left = 0;
        int right = citations.length + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(citations, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public boolean check(int[] citations, int mid) {
        int count = 0;
        for (int citation : citations) {
            if (citation >= mid) {
                count++;
            }
        }
        return count >= mid;
    }
}
